from Code_Link_02 import ListNode
from Code_Link_02 import printLink
'''
原文：
https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html#%E6%80%9D%E8%B7%AF

题意：
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
'''
class MyLinkedList:

    def __init__(self):
        self.dummy_head = ListNode() #虚拟头节点，不是真正的头节点
        self.size = 0 #链表长度，初始化为0
        pass

    def get(self, index: int) -> int:
        if index > self.size -1 or index < 0: #当索引index是负数无效，索引值小于当前长度-1无效（索引从0开始计数，长度>=索引+1）
            return -1
        cur = self.dummy_head.next #虚拟头节点的下一节点就是真正的头节点
        for i in range(self.size):
            if index == i:#直到当前index是第i个节点，返回当前索引的val值
                return cur.val
            cur = cur.next#不是，跳到下一节点
        return -1


    '''
    addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
    '''

    def addAtHead(self, val: int) -> None:
        node = ListNode(val)
        node.next = self.dummy_head.next #新节点下一节点是虚拟头节点的下一节点
        self.dummy_head.next = node #虚拟头节点的下一节点指向node，node成为真正的头节点
        self.size += 1
        #printLink(self.dummy_head)
        pass

    def addAtTail(self, val: int) -> None:
        cur = self.dummy_head
        while cur.next != None:
            cur = cur.next #cur一直指到尾节点
        tail = ListNode(val)
        cur.next = tail # #cur尾节点指向tail节点，tail成为尾节点
        self.size += 1
        #printLink(self.dummy_head)
        pass

    '''
    addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。
                           如果 index 等于链表的长度，则该节点将附加到链表的末尾。
                           如果 index 大于链表长度，则不会插入节点。
                           如果 index 小于0，则在头部插入节点。
    在链表的下标是index节点前添加val，
    index <= 0 添加头节点
    index = size 添加尾节点
    其他无效
    '''
    def addAtIndex(self, index: int, val: int) -> None:

        if index <=0 :
            self.addAtHead(val)
        elif index == self.size:
            self.addAtTail(val)
        elif index > self.size:
            return
        else:
            cur = self.dummy_head
            for i in range(index):
                cur = cur.next
            tmp = ListNode(val)
            tmp.next = cur.next
            cur.next = tmp
            self.size += 1

            pass

        #printLink(self.dummy_head)
        return
        pass

    ''' 
    删除下标为index的节点
    index==0 删除头节点
    index==size-1 删除尾节点
    cur下标为index节点的上一节点
        当不是尾节点时：cur.next = cur.next.next
        是尾节点cur.next = None
    '''
    def deleteAtIndex(self, index: int) -> None:
        #无效情况 index<0, index >size超出索引，size==0空链表
        if index < 0 or index > self.size -1 or self.size == 0:return
        pre = self.dummy_head
        while index > 0:
            index -= 1
            pre = pre.next #cur为下标index的前一节点
        cur = pre.next
        if cur.next:
            pre.next = cur.next #下标index节点不是尾节点，前一节点指向当前节点的下一节点，删除了cur当前节点
        else:
            pre.next = None #cur是尾节点，直接pre下一节点为空
        self.size -= 1
        #printLink(self.dummy_head)

        pass
    def printLinkList(self):
        res = []
        cur = self.dummy_head.next
        while cur:
            res.append(cur.val)
            cur = cur.next
        #print("res:",res)
        return res

if __name__ =='__main__':
    index = 1
    val = 8
    obj = MyLinkedList()
    obj.addAtHead(1)
    obj.printLinkList()
    obj.addAtHead(2)
    obj.printLinkList()
    obj.addAtTail(3)
    obj.printLinkList()
    obj.addAtIndex(0,11)
    obj.printLinkList()
    obj.addAtIndex(4,12)
    obj.printLinkList()
    obj.addAtIndex(41,1992)
    obj.printLinkList()
    obj.addAtIndex(1,100)
    #obj.deleteAtIndex(4)
    obj.get(2)

# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)